#include"../include/rbtree.h"
RBTreeNode* create_node(void *key, void *value) {  
    RBTreeNode *node = malloc(sizeof(RBTreeNode));  
    node->key = key;  
    node->value = value;  
    node->color = RED; // 新节点总是红色  
    node->left = NULL;  
    node->right = NULL;  
    node->parent = NULL;  
    return node;  
}  
void left_rotate(RBTree *tree, RBTreeNode *x) {  
    RBTreeNode *y = x->right;  
    x->right = y->left;  
    if (y->left != NULL)  
        y->left->parent = x;  

    y->parent = x->parent;  
    if (x->parent == NULL) {  
        tree->root = y;  
    } else if (x == x->parent->left) {  
        x->parent->left = y;  
    } else {  
        x->parent->right = y;  
    }  

    y->left = x;  
    x->parent = y;  
}  

void right_rotate(RBTree *tree, RBTreeNode *y) {  
    RBTreeNode *x = y->left;  
    y->left = x->right;  
    if (x->right != NULL)  
        x->right->parent = y;  

    x->parent = y->parent;  
    if (y->parent == NULL) {  
        tree->root = x;  
    } else if (y == y->parent->left) {  
        y->parent->left = x;  
    } else {  
        y->parent->right = x;  
    }  

    x->right = y;  
    y->parent = x;  
}  
void fix_violation(RBTree *tree, RBTreeNode *node) {  
    RBTreeNode *parent = NULL;  
    RBTreeNode *grandparent = NULL;  

    while ((node != tree->root) && (node->color == RED) && (node->parent->color == RED)) {  
        parent = node->parent;  
        grandparent = parent->parent;  

        // 父节点是祖父节点的左子节点  
        if (parent == grandparent->left) {  
            RBTreeNode *uncle = grandparent->right;  

            // 情况 1：叔叔节点也是红色  
            if (uncle != NULL && uncle->color == RED) {  
                grandparent->color = RED;  
                parent->color = BLACK;  
                uncle->color = BLACK;  
                node = grandparent; // 继续修复 grandparent  
            } else {  
                // 情况 2：node 是右子节点  
                if (node == parent->right) {  
                    left_rotate(tree, parent);  
                    node = parent;  
                    parent = node->parent;  
                }  
                // 情况 3：node 是左子节点  
                right_rotate(tree, grandparent);  
                Color temp = parent->color;  
                parent->color = grandparent->color;  
                grandparent->color = temp;  
                node = parent; // 继续检查  
            }  
        } else { // 父节点是祖父节点的右子节点  
            RBTreeNode *uncle = grandparent->left;  

            // 情况 1：叔叔节点也是红色  
            if (uncle != NULL && uncle->color == RED) {  
                grandparent->color = RED;  
                parent->color = BLACK;  
                uncle->color = BLACK;  
                node = grandparent; // 继续修复 grandparent  
            } else {  
                // 情况 2：node 是左子节点  
                if (node == parent->left) {  
                    right_rotate(tree, parent);  
                    node = parent;  
                    parent = node->parent;  
                }  
                // 情况 3：node 是右子节点  
                left_rotate(tree, grandparent);  
                Color temp = parent->color;  
                parent->color = grandparent->color;  
                grandparent->color = temp;  
                node = parent; // 继续检查  
            }  
        }  
    }  
    tree->root->color = BLACK; // 根节点始终是黑色  
}  

void RB_insert(RBTree *tree, void *key, void *value) {  
    RBTreeNode *newNode = create_node(key, value);  
    // 检查树是否为空  
    if (tree->root == NULL) {  
        newNode->color = BLACK; // 根节点颜色为黑色  
        tree->root = newNode;  
        tree->size++; // 更新树的大小  
        return;  
    }  

    RBTreeNode *parent = NULL;  
    RBTreeNode *current = tree->root;  

    // 寻找插入位置  
    while (current != NULL) {  
        parent = current;  
        if (tree->compare(key, current->key) < 0) {  
            current = current->left;  
        } else {  
            current = current->right;  
        }  
    }  

    newNode->parent = parent;  

    if (tree->compare(key, parent->key) < 0) {  
        parent->left = newNode;  
    } else {  
        parent->right = newNode;  
    }  
    tree->size++; // 更新树的大小  
    fix_violation(tree, newNode);  
}  
RBTreeNode* search(RBTree *tree, void *key) {  
    RBTreeNode *current = tree->root;  
    while (current != NULL) {  
        int cmp = tree->compare(key, current->key);  
        if (cmp == 0) {  
            return current; // 找到节点  
        } else if (cmp < 0) {  
            current = current->left;  
        } else {  
            current = current->right;  
        }  
    }  
    return NULL; // 未找到  
}  
void fix_double_black(RBTree *tree, RBTreeNode *x) {  
    if (x == tree->root) return; // 根节点  

    RBTreeNode *sibling = (x == x->parent->left) ? x->parent->right : x->parent->left;  
    RBTreeNode *parent = x->parent;  

    if (sibling == NULL) { // 兄弟节点不存在  
        fix_double_black(tree, parent);  
    } else {  
        if (sibling->color == RED) { // 兄弟节点为红  
            parent->color = RED;  
            sibling->color = BLACK;  
            if (sibling == parent->left) {  
                right_rotate(tree, parent);  
            } else {  
                left_rotate(tree, parent);  
            }  
            fix_double_black(tree, x); // 再次检查  
        } else {  
            // 兄弟节点为黑  
            if ((sibling->left != NULL && sibling->left->color == RED) ||  
                (sibling->right != NULL && sibling->right->color == RED)) {  
                
                if (sibling->left != NULL && sibling->left->color == RED) {  
                    if (sibling == parent->left) {  
                        sibling->left->color = sibling->color;  
                        sibling->color = parent->color;  
                        right_rotate(tree, parent);  
                    } else {  
                        sibling->left->color = parent->color;  
                        right_rotate(tree, sibling);  
                        left_rotate(tree, parent);  
                    }  
                } else {  
                    if (sibling == parent->left) {  
                        sibling->right->color = parent->color;  
                        left_rotate(tree, sibling);  
                        right_rotate(tree, parent);  
                    } else {  
                        sibling->right->color = sibling->color;  
                        sibling->color = parent->color;  
                        left_rotate(tree, parent);  
                    }  
                }  
                parent->color = BLACK;  
            } else {  
                sibling->color = RED;  
                if (parent->color == BLACK) {  
                    fix_double_black(tree, parent);  
                } else {  
                    parent->color = BLACK;  
                }  
            }  
        }  
    }  
}  

// 删除节点  
void delete_node(RBTree *tree, void *key) {  
    RBTreeNode *node = search(tree, key);  
    if (node == NULL) return; // 未找到节点  

    RBTreeNode *y = node;  
    RBTreeNode *x;  
    Color original_color = y->color;  

    if (node->left == NULL) {  
        x = node->right;  
        if (y->parent == NULL) {  
            tree->root = x;  
        } else if (y == y->parent->left) {  
            y->parent->left = x;  
        } else {  
            y->parent->right = x;  
        }  
        if (x != NULL) x->parent = y->parent;  
        free(node);  
    } else if (node->right == NULL) {  
        x = node->left;  
        if (y->parent == NULL) {  
            tree->root = x;  
        } else if (y == y->parent->left) {  
            y->parent->left = x;  
        } else {  
            y->parent->right = x;  
        }  
        if (x != NULL) x->parent = y->parent;  
        free(node);  
    } else {  
        y = node->right;  
        while (y->left != NULL) {  
            y = y->left;  
        }  
        original_color = y->color;  
        x = y->right;  
        if (y->parent == node) {  
            if (x != NULL) x->parent = y;  
        } else {  
            if (x != NULL) x->parent = y->parent;  
            y->parent->left = x;  
            y->right = node->right;  
            node->right->parent = y;  
        }  
        if (node->parent == NULL) {  
            tree->root = y;  
        } else if (node == node->parent->left) {  
            node->parent->left = y;  
        } else {  
            node->parent->right = y;  
        }  
        y->parent = node->parent;  
        y->color = node->color;  
        y->left = node->left;  
        node->left->parent = y;  
        free(node);  
    }  

    if (original_color == BLACK) {  
        fix_double_black(tree, x);  
    }  
}  

void inorder_traversal(RBTreeNode *node, Array *array, int *index) {  
    if (node == NULL) return;  

    // 先遍历左子树  
    inorder_traversal(node->left, array, index);  

    // 将当前节点的键添加到数组  
    array->value[*index] = node->value;  
    array->key[(*index)++] = node->key;  

    // 再遍历右子树  
    inorder_traversal(node->right, array, index);  
}  
Array* tree_to_array(RBTree *tree) {  
    Array *array = malloc(sizeof(Array));  
    array->key = malloc(tree->size * sizeof(void *)); // 假设我们有一个 size 字段来跟踪树的大小  
    array->value = malloc(tree->size * sizeof(void *)); // 假设我们有一个 size 字段来跟踪树的大小  
    array->size = tree->size;  

    int index = 0;  
    inorder_traversal(tree->root, array, &index);  
    return array;  
}  
